package com.mathstruct;

public class Fig10_53 {

    public static final int NOT_A_VERTEX = -1;

    /**
     * Compute all-shortest paths. a[ ][ ] contains the adjacency matrix with a[ i ][ i ] presumed to
     * be zero. d[ ] contains the values of the shortest path. Vertices are numbered starting at 0;
     * all arrays have equal dimension. A negative cycle exists if d[ i ][ i ] is set to a negative
     * value. Actual path can be computed using path[ ][ ]. NOT_A_VERTEX is -1
     */
    public static void allPairs(int[][] a, int[][] d, int[][] path) {
        int n = a.length;

        // Initialize d and path
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = a[i][j];
                path[i][j] = NOT_A_VERTEX;
            }
        }

        for (int k = 0; k < n; k++)
        // Consider each vertex as an intermediate
        {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (d[i][k] + d[k][j] < d[i][j]) {
                        // Update shortest path
                        d[i][j] = d[i][k] + d[k][j];
                        path[i][j] = k;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] a = {{0, 2, -2, 2}, {1000, 0, -3, 1000}, {4, 1000, 0, 1000}, {1000, -2, 3, 0}};
        int d[][] = new int[4][4];
        int path[][] = new int[4][4];

        allPairs(a, d, path);
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.print(d[i][j] + "    ");
            }
            System.out.println();
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.print(path[i][j] + "    ");
            }
            System.out.println();
        }
    }
}
